package com.problem.leetcode;

/**
 * Given a sorted array and a target value,
 * return the index if the target is found. If not,
 * return the index where it would be if it were inserted in order.
 * You may assume no duplicates in the array.
 *
 * 思路:二分查找法的变种，就是要处理终止条件的逻辑，begin=end的时候有可能还是没有找到元素，所以要判断nums[begin]与target的大小
 *
 * @author yanzhuoleo
 * @version V1.0
 * @Description: Problem35
 * @date 2018-01-05-下午5:39
 */

public class Problem35 {
    public static void main(String[] args) {
        int result = searchInsert(new int[]{1, 3, 5, 6}, 2);
        System.out.println(result);
    }

    public static int searchInsert(int[] nums, int target) {

        if (nums.length == 0 || target < nums[0]) {
            return 0;
        }

        if (target > nums[nums.length - 1]) {
            return nums.length;
        }

        return binarySearch(nums, 0, nums.length, target);
    }

    public static int binarySearch(int[] nums, int begin, int end, int target) {

        int result = -1;
        int middle = (end + begin) >> 1;

        while (begin < end) {
            if (begin < end && nums[middle] < target) {
                return binarySearch(nums, middle + 1, end, target);
            }

            if (begin < end && nums[middle] > target) {
                return binarySearch(nums, begin, middle, target);
            }

            if (nums[middle] == target) {
                return middle;
            }

        }

        if (begin == end) {
            if (nums[middle] == target || nums[middle] > target) {
                result = middle;
            }

            if (nums[middle] < target) {
                result = middle + 1;
            }
        }
        return result;
    }

}
